package binary_tree.Leetcode;

/**
 * 将BST转化为双向链表
 */
public class NowCoder_ConvertTree {
    //传入一棵以pRoot为根节点的BST就能转化为双向链表，返回链表的头节点
    public TreeNode Convert(TreeNode pRootOfTree){
        if(pRootOfTree==null){
            return null;
        }
        /**
         * 对树进行中序遍历
         * 此时的遍历=>转换操作=>先将左子树转为双向链表
         * 通过子函数就转了Convert(pRootOfTree.left)
         * 此时leftHead就是左链表的头节点
         */
        TreeNode leftHead=Convert(pRootOfTree.left);
        //继续处理根节点
        TreeNode leftTail=leftHead;
        //注意判空
        while (leftTail!=null&&leftTail.right!=null){
            leftTail=leftTail.right;
        }
        //此时leftTail就处在左侧链表的尾结点
        if(leftTail!=null){
            pRootOfTree.left=leftTail;
            leftTail.right=pRootOfTree;
        }
        //在递归处理右子树，转换右子树为链表，返回右子树链表的头节点
        TreeNode rightHead=Convert(pRootOfTree.right);
        if(rightHead!=null){
            //再将根节进行拼接
            pRootOfTree.right=rightHead;
            rightHead.left=pRootOfTree;
        }
        return leftHead==null? pRootOfTree:leftHead;
    }
}
